home *** CD-ROM | disk | FTP | other *** search
/ Gekkan Dennou Club 145 / Gekkan Dennou Club - 2000.6 Vol. 145 (Japan).7z / Gekkan Dennou Club - 2000.6 Vol. 145 (Japan) (Track 1).bin / docs / perl / perl18.doc < prev   
Text File  |  2000-04-22  |  28KB  |  928 lines
  1.  
  2.  
  3.  
  4.  
  5.                    おきらくＰｅｒｌプログラミング入門
  6.                       ～～めざせ Perl マスター～～
  7.  
  8.                                 広井  誠
  9.  
  10.                                 第１８回
  11.  
  12.  
  13.  
  14.  
  15. ○オブジェクト指向編（その４）
  16.  
  17.   前回は説明のためのプログラムしか示すことができなかったので、今回は継承
  18.  
  19. を使って具体的なプログラムを作ります。ところが、おもしろいアイデアがなか
  20.  
  21. なか浮かばずに先月は休載いたしましたが、今月も同じように苦しい状態です。
  22.  
  23. ここは開き直って、第 16 回で作成した二分探索木を継承して、「AVL 平衡木」
  24.  
  25. を作ることにしました。AVL 平衡木の操作は複雑で、継承の例題とするには不適
  26.  
  27. 切かもしれませんが、リファレンスの応用例にはなるでしょう。
  28.  
  29.  
  30. ○AVL 平衡木
  31.  
  32.   二分探索木では、最下層にあるデータを探す場合が最悪で、木の高さ分だけ比
  33.  
  34. 較が行われます。したがって、木の高さを低く抑えた方が探索効率も良くなりま
  35.  
  36. す。木の高さはデータ数を N とすると、データがランダムに挿入されればlog N
  37.  
  38. 程度に収まります。しかし、昇順にソートされたデータを挿入していくと、右側
  39.  
  40. の木にだけデータが追加され、線形探索と同じになってしまいます。二分探索木
  41.  
  42. の性能を十分に発揮させるには、左右の木のバランスが重要なのです。
  43.  
  44.   そこで、左右のバランスを一定の範囲に収める「平衡木」が考案されています。
  45.  
  46. 有名なところでは AVL 木、2-3 木、B 木、B* 木などがあります。この中で 2-3
  47.  
  48. 木、B 木、B* 木は多分木、AVL 木は二分木を使用します。
  49.  
  50.   AVL 木は、1962 年に Adel'son-Vel'skii と Landis が考案したもので、考案
  51.  
  52. 者の頭文字をとって AVL 木と呼ばれています。AVL 木は最初に実現された平衡
  53.  
  54. 木として歴史的な意味で価値がありますが、性能的には B 木や B* 木の方が優
  55.  
  56. れています。多分木を使う場合、原理的に難しいことはないのですが、実際のプ
  57.  
  58. ログラムは相当に複雑になります。興味のある方は参考文献[2] を読んでみてく
  59.  
  60. ださい。
  61.  
  62.   AVL 木は「Ｚしーモンキーほしゅうの時間その１０(月刊・電脳倶楽部 Vol.95
  63.  
  64. ZFIX10.DOC )」でも説明しました。そこで、AVL 木の説明は ZFIX10.DOC から抜
  65.  
  66. 粋します。
  67.  
  68.  
  69. ━━  ここから ZFIX10.DOC の抜粋  ━━
  70.  
  71.   木の高さを一定レベルに抑えるデータ構造に「AVL 平衡木」があります。この
  72.  
  73. 方法は、左右の部分木の高さを計算し、その差が 1 より大きくなったならば、
  74.  
  75. それを 1 以下になるように修正することで、全体の木の高さを抑えようとする
  76.  
  77. ものです。
  78.  
  79.   n 個の節を持つ二分探索木の高さは、節が左右に均等に分配されれば、log n
  80.  
  81. 程度に収まります。参考文献 [1] によれば、「AVL 平衡木では、この 1.5 倍程
  82.  
  83. 度の高さに収まる。」とのことです。したがって、100 万個のデータに対して木
  84.  
  85. の高さは 30 程度に収まることになります。
  86.  
  87.  
  88.   それでは、どのように木の構成を修正するのか、見ていくことにしましょう。
  89.  
  90.   左右の木の高さの差を「平衡度」という数値を使って表しましょう。新しい節
  91.  
  92. を追加した場合、その親の節で平衡度が崩れます。新しい節は子を持っていない
  93.  
  94. ので、平衡度は均衡していると考えられるので 0 とします。そして、左側に新
  95.  
  96. しい子を追加した場合は、平衡度を 1 増やすことにし、右側に新しい子を追加
  97.  
  98. した場合は 1 減らすことにします。このようにすると、平衡度が 1 ならば左部
  99.  
  100. 分木が 1 つ高く、-1 ならば右部分木が 1 つ高い、ということになります。こ
  101.  
  102. のあと根の方向に向かって平衡度が崩れていないかチェックしていきます。そし
  103.  
  104. て、平衡度が -2 または 2 になったら、左右の部分木の高さを修正します。
  105.  
  106.   それでは、修正が必要な場合を考えていきましょう。
  107.  
  108.  
  109.                           平衡度                      平衡度
  110.                 Ａ        Ａ：1               Ａ      Ａ：2
  111.               ／  ＼                        ／  ＼
  112.             Ｂ      Ｃ    Ｂ：0           Ｂ      Ｃ  Ｂ：1
  113.           ／  ＼                        ／  ＼
  114.         Ｄ      Ｅ        Ｄ：0       Ｄ      Ｅ      Ｄ：1
  115.                                     ／
  116.                                   Ｆ                  Ｆ：0
  117.  
  118.  
  119.                       図 1 : ＬＬ１重回転（修正前）
  120.  
  121.  
  122.   上図を見てください。節Ａの平衡度は 1 で、その他の節の平衡度は 0 です。
  123.  
  124. この状態で、節Ｄの左側に節Ｆを追加します。Ｄの平衡度は 1 になります。そ
  125.  
  126. の親のＢは、左側の部分木で節が追加されたので、この平衡度も 1 になります。
  127.  
  128. そして、その親のＡも左部分木で追加が行われたので、平衡度が 1 つ増え 2 に
  129.  
  130. なり、修正が必要になります。この場合、平衡度が狂った節Ａと、その左側の節
  131.  
  132. Ｂを、順序関係が崩れないように交換します。これを「ＬＬ１重回転」といいま
  133.  
  134. す。修正後は次のようになります。
  135.  
  136.  
  137.                                           平衡度
  138.                             Ｂ            Ａ：0
  139.                           ／  ＼
  140.                         Ｄ      Ａ        Ｂ：0
  141.                       ／      ／  ＼
  142.                     Ｆ      Ｅ      Ｃ    Ｄ：1
  143.  
  144.  
  145.                     Ｆ < Ｄ < Ｂ < Ｅ < Ａ < Ｃ
  146.  
  147.                       図 2 : ＬＬ１重回転（修正後）
  148.  
  149.  
  150.   次も、左部分木が高くなる場合です。
  151.  
  152.  
  153.                           平衡度                        平衡度
  154.                 Ａ        Ａ：1               Ａ        Ａ：2
  155.               ／  ＼                        ／  ＼
  156.             Ｂ     Ｃ     Ｂ：0           Ｂ      Ｃ    Ｂ：-1
  157.           ／  ＼                        ／  ＼
  158.         Ｄ      Ｅ        Ｄ：0       Ｄ      Ｅ        Ｅ：1
  159.                                             ／
  160.                                           Ｆ            Ｆ：0
  161.  
  162.                       図 3 : ＬＲ２重回転（修正前）
  163.  
  164.  
  165.   今度は、節Ｅの左側に節Ｆを追加します。Ｅの平衡度は 1 になりますが、Ｂ
  166.  
  167. から見ると右側の部分木に追加されていますので、平衡度を 1 つ減らして -1
  168.  
  169. となります。その親のＡは、左側の部分木に追加されていますので、平衡度を 1
  170.  
  171. 増やし 2 になります。
  172.  
  173.   ＬＬ１重回転と同じく、節Ａの平衡度が 2 になりますが、節Ｂの平衡度が -1
  174.  
  175. になるので、区別することができます。この場合はＢとＥを交換してから、さら
  176.  
  177. にＥとＡを交換します。これを「ＬＲ２重回転」といいます。修正後は次のよう
  178.  
  179. になります。
  180.  
  181.  
  182.                                           平衡度
  183.                             Ｅ            Ａ：-1
  184.                           ／  ＼
  185.                         Ｂ      Ａ        Ｂ：0
  186.                       ／  ＼      ＼
  187.                     Ｄ      Ｆ      Ｃ    Ｅ：0
  188.  
  189.  
  190.                     Ｄ < Ｂ < Ｆ < Ｅ < Ａ < Ｃ
  191.  
  192.                       図 4 : ＬＲ２重回転（修正後）
  193.  
  194.  
  195.   節Ｆを節Ｅの右側に追加しても、ＬＲ２重回転となります。ただし、修正後の
  196.  
  197. 平衡度が異なります。
  198.  
  199.  
  200.                           平衡度                        平衡度
  201.                 Ａ        Ａ：2             Ｅ          Ａ：0
  202.               ／  ＼                      ／  ＼
  203.             Ｂ      Ｃ    Ｂ：-1        Ｂ      Ａ      Ｂ：1
  204.           ／  ＼                      ／      ／  ＼
  205.         Ｄ      Ｅ        Ｅ：-1    Ｄ      Ｆ      Ｃ  Ｅ：0
  206.                   ＼
  207.                     Ｆ    Ｆ：0
  208.  
  209.          (1) 修正前                     (2) 修正後
  210.  
  211.                     Ｄ < Ｂ < Ｅ < Ｆ < Ａ < Ｃ
  212.  
  213.                       図 5 : ＬＲ２重回転（その２）
  214.  
  215.  
  216.   右の部分木が高くなる場合を考えましょう。
  217.  
  218.  
  219.                           平衡度                       平衡度
  220.             Ａ            Ａ：-1       Ａ              Ａ：-2
  221.           ／  ＼                     ／  ＼
  222.         Ｂ      Ｃ        Ｃ：0    Ｂ      Ｃ          Ｃ：-1
  223.               ／  ＼                     ／  ＼
  224.             Ｄ      Ｅ    Ｅ：0        Ｄ      Ｅ      Ｅ：-1
  225.                                                  ＼
  226.                                                    Ｆ  Ｆ：0
  227.  
  228.                       図 6 : ＲＲ１重回転（修正前）
  229.  
  230.  
  231.   最初の状態は、節Ａからみて右部分木が高いので、平衡度は -1 になっていま
  232.  
  233. す。その他の節の平衡度は 0 です。この状態から節Ｅの右側に節Ｆを追加する
  234.  
  235. ことを考えます。節Ｅの平衡度は -1 になります。節Ｃの平衡度は、右側の部分
  236.  
  237. 木に追加されたので、1 つ減らして -1 になります。その親のＡは、これも右部
  238.  
  239. 分木に追加されているので、平衡度を 1 つ減らして -2 になり、修正が必要に
  240.  
  241. なります。この場合、二分探索木の条件を崩さないように、節Ａと節Ｃを交換し
  242.  
  243. ます。これを「ＲＲ１重回転」といいます。修正後は次のようになります。
  244.  
  245.  
  246.                                           平衡度
  247.                             Ｃ            Ａ：0
  248.                           ／  ＼
  249.                         Ａ      Ｅ        Ｃ：0
  250.                       ／  ＼      ＼
  251.                     Ｂ      Ｄ      Ｆ    Ｅ：-1
  252.  
  253.                     Ｂ < Ａ < Ｄ < Ｃ < Ｅ < Ｆ
  254.  
  255.                       図 7 : ＲＲ１重回転（修正後）
  256.  
  257.  
  258.   １重回転の次は、２重回転です。
  259.  
  260.  
  261.                           平衡度                   平衡度
  262.             Ａ            Ａ：-1       Ａ          Ａ：-2
  263.           ／  ＼                     ／  ＼
  264.         Ｂ      Ｃ        Ｃ：0    Ｂ      Ｃ      Ｃ：1
  265.               ／  ＼                     ／  ＼
  266.             Ｄ      Ｅ    Ｄ：0        Ｄ      Ｅ  Ｄ：1
  267.                                      ／
  268.                                    Ｆ              Ｆ：0
  269.  
  270.                       図 8 : ＲＬ２重回転（修正前）
  271.  
  272.  
  273.   節Ｄの左側に節Ｆを追加します。Ｄの平衡度は 1 になります。節Ｃは、左部
  274.  
  275. 分木に追加されたので、平衡度を１つ増やして 1 になります。その親のＡは、
  276.  
  277. 右部分木に追加されたので、平衡度を１つ減らして -2 となります。
  278.  
  279.   ＲＲ１重回転と同様に、節Ａの平衡度は -2 ですが、節Ｃの平衡度が 1 なの
  280.  
  281. で区別することができます。この場合、二分探索木の構成を崩さないように、節
  282.  
  283. Ｄと節Ｃを交換して、さらに節Ｄと節Ａを交換します。これを「ＲＬ２重回転」
  284.  
  285. といいます。修正後は次のようになります。
  286.  
  287.  
  288.                                          平衡度
  289.                             Ｄ           Ａ：0
  290.                           ／  ＼
  291.                         Ａ      Ｃ       Ｃ：-1
  292.                       ／  ＼      ＼
  293.                     Ｂ      Ｆ      Ｅ   Ｄ：0
  294.  
  295.                     Ｂ < Ａ < Ｆ < Ｄ < Ｃ < Ｅ
  296.  
  297.                       図 9 : ＲＬ２重回転（修正後）
  298.  
  299.  
  300.   節Ｄの右側に節Ｆを追加してもＲＬ２重回転となりますが、修正後の平衡度が
  301.  
  302. 異なります。
  303.  
  304.  
  305.                           平衡度                        平衡度
  306.             Ａ            Ａ：-2            Ｄ          Ａ：1
  307.           ／  ＼                          ／  ＼
  308.         Ｂ      Ｃ        Ｃ：1         Ａ      Ｃ      Ｃ：0
  309.               ／  ＼                  ／      ／  ＼
  310.             Ｄ      Ｅ    Ｄ：-1    Ｂ      Ｆ      Ｅ  Ｄ：0
  311.               ＼
  312.                 Ｆ        Ｆ：0
  313.  
  314.         (1) 修正前                      (2) 修正後
  315.  
  316.                    Ｂ < Ａ < Ｄ < Ｆ < Ｃ < Ｅ
  317.  
  318.                      図 10 : ＲＬ２重回転（その２）
  319.  
  320.  
  321.   修正が必要なのは、以上６通りのパターンです。
  322.  
  323.  
  324. ━━  ここまで  ━━
  325.  
  326.   AVL 木は二分探索木の一種ですから、二分探索木を継承することでデータの探
  327.  
  328. 索と表示を行うメソッドをそのまま再利用することができます。データを挿入す
  329.  
  330. る場合、平衡度を修正する処理が必要になるので、データ挿入のメソッドはオー
  331.  
  332. バーライドしなければいけません。
  333.  
  334.   それでは具体的にプログラムします。最初にクラスと継承を設定します。
  335.  
  336.  
  337.      List 1 : クラスの設定
  338.  
  339.    1 use Bintree;
  340.    2
  341.    3 package Avltree;
  342.    4 @ISA = (Bintree);
  343.    5
  344.    6 # 終端を表す nil を再ブレスする
  345.    7 sub make_tree {
  346.    8   $nil = Bintree->make_tree();
  347.    9   bless $nil, 'Avltree';
  348.   10   $nil;
  349.   11 }
  350.  
  351.  
  352. 終端を表す $nil は、クラス  Bintree  で定義されたオブジェクトを使わない
  353.  
  354. と、データの探索や表示を行うメソッドは動作しません。そこで、AVL 木を初期
  355.  
  356. 化するメソッド make_tree で、Bintree->make_tree() を呼び出して終端を表す
  357.  
  358. オブジェクトを取得し、大域変数 $nil にセットしておきます。また、このオブ
  359.  
  360. ジェクトは  Bintree にブレスされているので、オーバーライドしたメソッドを
  361.  
  362. 動作させるために、Avltree に再ブレスしておきます。
  363.  
  364.   次は節を生成するメソッドを作ります。
  365.  
  366.  
  367.      List 2 : 節を作る
  368.  
  369.    1 sub new {
  370.    2   my ($type, $item) = @_;
  371.    3   my $obj = {
  372.    4     'item'    => $item,
  373.    5     'left'    => $nil,
  374.    6     'right'   => $nil,
  375.    7     'balance' => 0
  376.    8   };
  377.    9   bless $obj, $type;
  378.   10   $obj;
  379.   11 }
  380.  
  381.  
  382. 平衡度を表すため、節に新しい変数 balance を追加します。 新しい節なので、
  383.  
  384. 平衡度は 0 に初期化します。
  385.  
  386.  
  387. ○データの挿入
  388.  
  389.   次は、データの挿入を作成します。新しい節を挿入した場合、根の方に向かっ
  390.  
  391. て平衡度をチェックしていく処理が必要になります。二分探索木では、データの
  392.  
  393. 挿入を再帰呼び出しでプログラムしましたが、平衡度のチェックを組み込むには
  394.  
  395. 少々面倒なので、ループに展開することにします。単純なループでは、たどって
  396.  
  397. きた道筋がわからなくなるので、自前のスタックを用意して通過した節を記憶し
  398.  
  399. ます。プログラムは次のようになります。
  400.  
  401.  
  402.      List 3 : AVL 木へデータを挿入
  403.  
  404.    1 sub insert_tree {
  405.    2   my ($root, $item) = @_;
  406.    3   my @stack = ();
  407.    4   my $place = \$root;
  408.    5   while( $$place != $nil ){
  409.    6     my $node = $$place;
  410.    7     my $result = $item->compare( $node->{'item'} );
  411.    8     push( @stack, $node );
  412.    9     if( $result == 0 ){
  413.   10       return $root;                 # 同じデータ有り
  414.   11     } elsif( $result < 0 ){
  415.   12       $place = \$node->{'left'};
  416.   13     } else {
  417.   14       $place = \$node->{'right'};
  418.   15     }
  419.   16   }
  420.   17   my $obj = Avltree->new($item);
  421.   18   return $obj if $root == $nil;  # ルートに挿入
  422.   19   $$place = $obj;
  423.   20   &check_balance( $root, $obj, \@stack );
  424.   21 }
  425.  
  426.  
  427.   メソッド insert_tree は AVL 木のルートと挿入するデータを受け取り、挿入
  428.  
  429. した後の木を返します。これは二分探索木の場合と同じです。道筋を記憶するた
  430.  
  431. めに配列 @stack を用意します。変数 $place は、節を格納する変数を指し示す
  432.  
  433. リファレンスを格納します。$place の使い方が、このプログラムのポイントで
  434.  
  435. す。リファレンスを使うことで、そこに格納されている節を取り出したり、そこ
  436.  
  437. へ新しい節をセットすることができます。最初は $root へのリファレンスで初
  438.  
  439. 期化します。
  440.  
  441.   5 - 16 行目の while ループで、データを挿入する場所を求めるために木をた
  442.  
  443. どります。7 行目で、$place が指し示す変数から節を取り出し $node にセット
  444.  
  445. します。8 行目でデータを比較し、9 行目で節 $node を @stack に格納します。
  446.  
  447. $result が 0 より小さい場合は $place に $node->{'left'} へのリファレンス
  448.  
  449. を、大きい場合は $node->{'right'} へのリファレンスをセットします。これで
  450.  
  451. $$place とすれば、次の節にアクセスすることができます。
  452.  
  453.   ループを抜けたら、新しい節を作成して木に挿入します。$root が $nil であ
  454.  
  455. れば空の木なので、新しい節 $obj を返します。そうでなければ、木に新しい節
  456.  
  457. $obj を挿入します。$place は $node->{'left'} か $node->{'right'} へのリ
  458.  
  459. ファレンスなので、$$place に $obj を代入するだけで、正しい位置に節が挿入
  460.  
  461. されます。最後に、関数 check_balance を呼び出して、木の平衡度をチェック
  462.  
  463. します。この時、ルートを書き換える場合があるので、check_balance でルート
  464.  
  465. を返すようにします。
  466.  
  467.  
  468. ○平衡度のチェック
  469.  
  470.   次は check_balance を作ります。
  471.  
  472.  
  473.      List 4 : バランスのチェック
  474.  
  475.    1 sub check_balance {
  476.    2   my ($root, $node, $stack) = @_;
  477.    3   my $cnode = $nil;
  478.    4   my ($b, $pnode);
  479.    5   for( ; @$stack > 0; $node = $pnode ){
  480.    6     $pnode = pop( @$stack );
  481.    7     if( $pnode->{'left'} == $node ){
  482.    8       $b = ++$pnode->{'balance'};
  483.    9     } else {
  484.   10       $b = --$pnode->{'balance'};
  485.   11     }
  486.   12     return $root if $b == 0;    # 書き換え必要無し
  487.   13     if( $b > 1 ){
  488.   14       $cnode = &LR_rotate( $node, $pnode );
  489.   15       last;
  490.   16     } elsif( $b < -1 ) {
  491.   17       $cnode = &RL_rotate( $node, $pnode );
  492.   18       last;
  493.   19     }
  494.   20   }
  495.   21   # 子の付け替え処理(List 5)
  496.   22 }
  497.  
  498.  
  499.   スタックに積まれた節を取りだして、平衡度をチェックしていきます。$node
  500.  
  501. は、新しい節が追加された部分木を表します。この関数が呼び出された時は、新
  502.  
  503. しく追加された節が渡されます。$node の親を $pnode とします。5 行目の for
  504.  
  505. ループで、スタックにデータがある間、平衡度をチェックします。6 行目で、ス
  506.  
  507. タックから $node の親を取り出して $pnode にセットします。7 行目で、$node
  508.  
  509. が $pnode の left か right のどちらに挿入されているか調べます。left なら
  510.  
  511. ば平衡度を +1 し、right ならば -1 します。
  512.  
  513.   12 行目で、平衡度 $b が 0 ならば木のバランスは保たれているので、それ以
  514.  
  515. 上チェックする必要はありません。ルートは変更する必要がないので、$root を
  516.  
  517. そのまま返します。
  518.  
  519.   13 行目で、$b が 1 より大きくなったのであれば、木を修正する必要があり
  520.  
  521. ます。この場合は、左部分木が大きいのでＬＬ１重回転かＬＲ２重回転の処理が
  522.  
  523. 必要です。この処理は LR_rotate で行います。この関数は修正後の部分木を返
  524.  
  525. すので、それを $cnode に格納してループを抜けます。
  526.  
  527.   16 行目で、$b が -1 より小さいのであれば、右部分木が大きくなったので、
  528.  
  529. ＲＲ１重回転かＲＬ２重回転の処理が必要になります。この処理は RL_rotateで
  530.  
  531. 行います。
  532.  
  533.   これ以外は、修正が必要なほど平衡度が崩れていない場合です。$node を
  534.  
  535. $pnode に更新して、次の親をチェックします。
  536.  
  537.   ループを抜けた後、平衡度が崩れた部分木は修正されていますが、その部分木
  538.  
  539. を持つ節の書き換えが済んでいません。次の図を見てください。
  540.  
  541.  
  542.  
  543.         Ｐ                平衡度        Ｐ              平衡度
  544.           ＼                              ＼
  545.             Ａ            Ａ：-2            Ｄ          Ａ：1
  546.           ／  ＼                          ／  ＼
  547.         Ｂ      Ｃ        Ｃ：1         Ａ      Ｃ      Ｃ：0
  548.               ／  ＼                  ／      ／  ＼
  549.             Ｄ      Ｅ    Ｄ：-1    Ｂ      Ｆ      Ｅ  Ｄ：0
  550.               ＼
  551.                 Ｆ        Ｆ：0
  552.  
  553.         (1) 修正前                      (2) 修正後
  554.  
  555.  
  556.              図 11 : 子の付け替えが必要（例：ＲＬ２重回転）
  557.  
  558.  
  559. 図 11 において、節Ａで木の修正が行われた場合、節Ｐの右側の子をＡからＤに
  560.  
  561. 付け替えなければいけません。回転処理を行う関数は、節Ｄを返しますので、子
  562.  
  563. の付け替え処理を行います。
  564.  
  565.  
  566.      List 5 : 子の付け替え処理
  567.  
  568.    1   if( @$stack > 0 ){
  569.    2     my $ppnode = pop( @$stack );
  570.    3     if( $ppnode->{'left'} == $pnode ){
  571.    4       $ppnode->{'left'} = $cnode;
  572.    5     } else {
  573.    6       $ppnode->{'right'} = $cnode;
  574.    7     }
  575.    8   } elsif( $cnode != $nil ){
  576.    9     return $cnode;
  577.   10   }
  578.   11   $root;
  579.  
  580.  
  581.   もしスタックにデータがあれば、そこから節を取り出して $ppnode にセット
  582.  
  583. します。この節は $pnode の親なので、$pnode が格納されている変数に $cnode
  584.  
  585. をセットします。スタックにデータがない場合は、ルートを書き換えるため
  586.  
  587. $cnode を返します。ただし、$cnode が NULL の場合は、部分木の修正が行われ
  588.  
  589. ていないので $root をそのまま返します。
  590.  
  591.  
  592. ○バランスの修正
  593.  
  594.   後は、部分木を修正する回転処理です。これは、図を見ながらコーディングす
  595.  
  596. るだけです。この処理を行う関数には、平衡度の崩れた節を $pnode とし、その
  597.  
  598. 子を $node として渡します。まずＬＲ回転処理からです。$node の平衡度が -1
  599.  
  600. の場合はＬＲ２重回転です。
  601.  
  602.  
  603.         Ａ：$pnode, Ｂ：$node, Ｅ：$cnode にあたる
  604.  
  605.                           平衡度                       平衡度
  606.                 Ａ        Ａ：2            Ｅ          Ａ：0
  607.               ／  ＼                     ／  ＼
  608.             Ｂ      Ｃ    Ｂ：-1       Ｂ      Ａ      Ｂ：1
  609.           ／  ＼                     ／      ／  ＼
  610.         Ｄ      Ｅ        Ｅ：-1   Ｄ      Ｆ      Ｃ  Ｅ：0
  611.                   ＼
  612.                     Ｆ    Ｆ：0
  613.  
  614.          (1) 修正前                     (2) 修正後
  615.  
  616.         Ａ->{'left'}  = Ｅ->{'right'};
  617.         Ｂ->{'right'} = Ｅ->{'left'};
  618.         Ｅ->{'right'} = Ａ;
  619.         Ｅ->{'left'}  = Ｂ;
  620.  
  621.                 図 12 : ＬＲ２重回転のポインタの付け替え
  622.  
  623.  
  624.   図の例では、Ｅ->{'left'} は $nil ですので、Ｂ->{'right'} に直接 $nil
  625.  
  626. をセットしたくなりますが、ＬＲ２重回転の場合は、Ｅ->{'right'} が $nil で
  627.  
  628. Ｅ->{'left'}  に節がある、という別パターンがありますので、直接 $nil をセ
  629.  
  630. ットしてはいけません。
  631.  
  632.   ポインタを付け替えたら平衡度を書き換えます。$cnode の平衡度によって
  633.  
  634. $pnode と $node の平衡度が違いますので、注意してください。
  635.  
  636.   $node の平衡度が -1 以外であればＬＬ１重回転です。これも図を見たほうが
  637.  
  638. わかりやすいでしょう。
  639.  
  640.  
  641.         Ａ：$pnode, Ｂ：$node にあたる
  642.  
  643.                         平衡度                        平衡度
  644.                 Ａ      Ａ：2             Ｂ          Ａ：0
  645.               ／  ＼                    ／  ＼
  646.             Ｂ      Ｃ  Ｂ：1         Ｄ      Ａ      Ｂ：0
  647.           ／  ＼                    ／      ／  ＼
  648.         Ｄ      Ｅ      Ｄ：1     Ｆ      Ｅ      Ｃ  Ｄ：1
  649.       ／
  650.     Ｆ                  Ｆ：0
  651.  
  652.           (1) 修正前                      (2) 修正後
  653.  
  654.           Ａ->{'left'}  = Ｂ->{'right'};
  655.           Ｂ->{'right'} = Ａ;
  656.  
  657.                 図 13 : ＬＬ１重回転のポインタの付け替え
  658.  
  659.  
  660.   後は $pnode と $node の平衡度を 0 にすれば修正完了です。ＬＬ１重回転の
  661.  
  662. 場合、Ｂが関数の返り値になります。
  663.  
  664.   これをプログラムすると、次のようになります。
  665.  
  666.  
  667.      List 6 : LR 回転
  668.  
  669.    1 sub LR_rotate {
  670.    2   my ($node, $pnode) = @_;
  671.    3   my $cnode, $b;
  672.    4   if( $node->{'balance'} < 0 ){
  673.    5     $cnode = $node->{'right'};
  674.    6     $pnode->{'left'} = $cnode->{'right'};
  675.    7     $node->{'right'} = $cnode->{'left'};
  676.    8     $cnode->{'right'} = $pnode;
  677.    9     $cnode->{'left'} = $node;
  678.   10     if( $cnode->{'balance'} > 0 ){
  679.   11       $pnode->{'balance'} = -1;
  680.   12       $node->{'balance'} = 0;
  681.   13     } elsif( $cnode->{'balance'} < 0 ){
  682.   14       $pnode->{'balance'} = 0;
  683.   15       $node->{'balance'} = 1;
  684.   16     } else {
  685.   17       $pnode->{'balance'} = 0;
  686.   18       $node->{'balance'} = 0;
  687.   19     }
  688.   20     $cnode->{'balance'} = 0;
  689.   21   } else {
  690.   22     $pnode->{'left'} = $node->{'right'};
  691.   23     $node->{'right'} = $pnode;
  692.   24     $pnode->{'balance'} = 0;
  693.   25     $node->{'balance'} = 0;
  694.   26     $cnode = $node;
  695.   27   }
  696.   28   $cnode;
  697.   29 }
  698.  
  699.  
  700.   プログラムは少々長いですが、図と同じように節を付け替えているだけです。
  701.  
  702. ＬＲ２重回転の場合、$node と $pnode の平衡度は $cnode の平衡度により異な
  703.  
  704. り、次の３通りの場合があります。
  705.  
  706.  
  707.         Ａ：$pnode, Ｂ：$node, Ｅ：$cnode にあたる
  708.  
  709.                           平衡度                       平衡度
  710.                 Ａ        Ａ：2            Ｅ          Ａ：0
  711.               ／  ＼                     ／  ＼
  712.             Ｂ      Ｃ    Ｂ：-1       Ｂ      Ａ      Ｂ：1
  713.           ／  ＼                     ／      ／  ＼
  714.         Ｄ      Ｅ        Ｅ：-1   Ｄ      Ｆ      Ｃ  Ｅ：0
  715.                   ＼
  716.                     Ｆ    Ｆ：0
  717.  
  718.              修正前                         修正後
  719.  
  720.                 (1) $cnode の平衡度が -1 の場合
  721.  
  722.                           平衡度                       平衡度
  723.                 Ａ        Ａ：2            Ｅ          Ａ：-1
  724.               ／  ＼                     ／  ＼
  725.             Ｂ      Ｃ    Ｂ：-1       Ｂ      Ａ      Ｂ：0
  726.           ／  ＼                     ／  ＼      ＼
  727.         Ｄ      Ｅ        Ｅ：1    Ｄ      Ｆ      Ｃ  Ｅ：0
  728.               ／
  729.             Ｆ            Ｆ：0
  730.  
  731.              修正前                         修正後
  732.  
  733.                 (2) $cnode の平衡度が 1 の場合
  734.  
  735.                           平衡度                        平衡度
  736.                 Ａ        Ａ：2             Ｅ          Ａ：0
  737.               ／                          ／  ＼
  738.             Ｂ            Ｂ：-1        Ｂ      Ａ      Ｂ：0
  739.               ＼
  740.                 Ｅ        Ｅ：0                         Ｅ：0
  741.  
  742.              修正前                         修正後
  743.  
  744.                 (3) $cnode の平衡度が 0 の場合
  745.  
  746.  
  747.                     図 14 : 平衡度の書き換え
  748.  
  749.  
  750. 「Ｚしーモンキーほしゅうの時間その１０(月刊・電脳倶楽部 Vol.95 ZFIX10.DOC)」
  751.  
  752. で作成したプログラムは、図 14 (3) のチェックが抜けていたため、平衡度の値
  753.  
  754. がおかしくなる不具合が発生します。なんとまあ、４年前に作ったプログラムの
  755.  
  756. バグを見つけることになるとは思ってもいませんでした。開き直って、AVL 木を
  757.  
  758. 取り上げて良かったということでしょうか（笑）。
  759.  
  760.   まあ、木のバランスは少々おかしくなりますが、二分探索木としての機能は正
  761.  
  762. 常に動作します。どの程度の影響があるのか、実際にプログラムを修正して試し
  763.  
  764. てみました。すると、データの比較回数は 1 - 2 % 減少しますが、実行速度は
  765.  
  766. わずかながら遅くなってしまいました。つまり、AVL 木ではバランスの修正に時
  767.  
  768. 間がかかるのです。AVL 木には実用的な価値があまりないと評価されるのも、こ
  769.  
  770. れが原因なのです。
  771.  
  772.  
  773.   ＲＲ１重回転とＲＬ２重回転の処理は、RL_rotate で行います。処理内容は
  774.  
  775. LR_rotate と同じなので、図のみ示すことにします。
  776.  
  777.  
  778.         Ａ：$pnode, Ｃ：$node にあたる
  779.  
  780.                           平衡度                          平衡度
  781.         Ａ                Ａ：-2              Ｃ          Ａ：0
  782.       ／  ＼                                ／  ＼
  783.     Ｂ      Ｃ            Ｃ：-1          Ａ      Ｅ      Ｃ：0
  784.           ／  ＼                        ／  ＼      ＼
  785.         Ｄ      Ｅ        Ｅ：-1      Ｂ      Ｄ      Ｆ  Ｅ：-1
  786.                   ＼
  787.                     Ｆ    Ｆ：0
  788.  
  789.         (1) 修正前                      (2) 修正後
  790.  
  791.                 Ａ->{'right'} = Ｃ->{'left'};
  792.                 Ｃ->{'left'}  = Ａ;
  793.  
  794.                 図 15 : ＲＲ１重回転のポインタの付け替え
  795.  
  796.  
  797.         Ａ：$pnode, Ｃ：$node, Ｄ：$cnode にあたる
  798.  
  799.                           平衡度                        平衡度
  800.             Ａ            Ａ：-2            Ｄ          Ａ：1
  801.           ／  ＼                          ／  ＼
  802.         Ｂ      Ｃ        Ｃ：1         Ａ      Ｃ      Ｃ：0
  803.               ／  ＼                  ／      ／  ＼
  804.             Ｄ      Ｅ    Ｄ：-1    Ｂ      Ｆ      Ｅ  Ｄ：0
  805.               ＼
  806.                 Ｆ        Ｆ：0
  807.  
  808.         (1) 修正前                      (2) 修正後
  809.  
  810.                 Ａ->{'right'} = Ｄ->{'left'};
  811.                 Ｃ->{'left'}  = Ｄ->{'right'};
  812.                 Ｄ->{'left'}  = Ａ;
  813.                 Ｄ->{'right'} = Ｃ;
  814.  
  815.                 図 16 : ＲＬ２重回転のポインタの付け替え
  816.  
  817.  
  818. プログラムの詳細はソースファイル avltree.pm を読んでください。
  819.  
  820.  
  821. ○実行結果
  822.  
  823.   それでは、実際に実行してみましょう。木の形を表示するために、データを表
  824.  
  825. 示する関数 print_tree_test を Bintree に追加します。
  826.  
  827.  
  828.      List 7 : 木の形を表示
  829.  
  830.    1 sub print_tree_test {
  831.    2   my ($node, $level) = @_;
  832.    3   my $i;
  833.    4   if( $node != $nil ){
  834.    5     &print_tree_test( $node->{'left'}, $level + 1 );
  835.    6     for( $i = 0; $i < $level; $i++ ){
  836.    7       print "  ";
  837.    8     }
  838.    9     $node->{'item'}->print_object();
  839.   10     &print_tree_test( $node->{'right'}, $level + 1 );
  840.   11   }
  841.   12 }
  842.  
  843.  
  844. データを出力する前に、レベル * 2 個の空白を出力します。これで木の形を表
  845.  
  846. すことができます。テストデータは第１６回と同様に数値とします。最初に二分
  847.  
  848. 探索木へ 1 から 7 までのデータを順番に挿入します。
  849.  
  850.  
  851.   # テストプログラム
  852.   $root = Bintree->make_tree();
  853.   for( $i = 1; $i <= 7; $i++ ){
  854.     my $obj = Number->new( $i );
  855.     $root = $root->insert_tree( $obj );
  856.   }
  857.   $root->print_tree_test( 0 );
  858.  
  859.  
  860.   実行結果
  861.  
  862.   1
  863.     2
  864.       3
  865.         4
  866.           5
  867.             6
  868.               7
  869.  
  870.  
  871. 実行結果を見ればおわかりのように、右側の木にしかデータが挿入されません。
  872.  
  873. これが二分探索木での最悪の状態です。では、AVL 木を使ってみましょう。
  874.  
  875.  
  876.   # テストプログラム
  877.   $root = Avltree->make_tree();
  878.   for( $i = 1; $i <= 7; $i++ ){
  879.     my $obj = Number->new( $i );
  880.     $root = $root->insert_tree( $obj );
  881.   }
  882.   $root->print_tree_test( 0 );
  883.  
  884.   実行結果
  885.  
  886.       1
  887.     2
  888.       3
  889.   4
  890.       5
  891.     6
  892.       7
  893.  
  894.  
  895. このように、木のバランスは完全に保たれています。プログラムは正常に動作し
  896.  
  897. ていますね。
  898.  
  899.  
  900. ○次回は？
  901.  
  902.   電脳倶楽部が Vol.147 で休刊になるのはとても残念です。残り２回しかあり
  903.  
  904. ませんが、最後まで続けるのでよろしくお付き合いくださいませ。次回は Perl
  905.  
  906. のオブジェクト指向と密接に関連しているパッケージ機能について、最終回は変
  907.  
  908. 数とクラスを結び付ける働きをするタイについて説明する予定です。お楽しみに。
  909.  
  910.  
  911.                               ―参考文献―
  912.  
  913.  
  914.  [1] 村田敏幸「X68000マシン語プログラミング 木探索」 Oh!X 1993 年 7 月号
  915.      ソフトバンク
  916.  
  917.  [2] 近藤嘉雪「定本Ｃプログラマのためのアルゴリズムとデータ構造」ソフト
  918.      バンク 1998
  919.  
  920.  [3] Larry Wall, Tom Christiansen, Randal L. Schwartz 共著「プログラミン
  921.      グＰｅｒｌ」改訂版 オライリー・ジャパン 1997
  922.  
  923.  [4] Sriram Srinivasan  著「実用Ｐｅｒｌプログラミング」オライリー・ジャ
  924.      パン 1998
  925.  
  926. （ＥＯＦ）
  927.  
  928.